package leetcode

func countPairs(deliciousness []int) int {
    // search for the max val in deliciousness
    maxVal := deliciousness[0]
    for _, val := range deliciousness {
        if val > maxVal {
            maxVal = val
        }
    }

    // set max sum as 2 * maxVal
    maxSum := maxVal * 2
    cnt := map[int]int{}

    ans := 0
    for _, val := range deliciousness {
        for sum := 1; sum <= maxSum; sum <<= 1 {
            ans += cnt[sum - val]
        }
        cnt[val] ++
    }

    return ans % (1e9 + 7)
}
